package mission4propre;

import java.util.LinkedList;

@SuppressWarnings("rawtypes")
public class AVLTree{

	private AVLNode root;
	 
	public AVLTree( ){
		root = null;
	}

	/**
	 * Insert into the tree; duplicates are ignored.
	 * @param x the item to insert.
	 */
	public void insert( Comparable x ){
		root = insert( x, root );
	}

	/**
	 * Test if the tree is logically empty.
	 * @return true if empty, false otherwise.
	 */
	public boolean isEmpty( )
	{
		return root == null;
	}

	/**
	 * Internal method to insert into a subtree.
	 * @param x the item to insert.
	 * @param t the node that roots the tree.
	 * @return the new root.
	 */
	
	@SuppressWarnings("unchecked")
	private AVLNode insert( Comparable x, AVLNode t )
	{
		if( t == null )
			t = new AVLNode( x, null, null );
		else if( x.compareTo( t.element ) <= 0 )
		{
			t.left = insert( x, t.left );
			if( height( t.left ) - height( t.right ) == 2 )
				if( x.compareTo( t.left.element ) <= 0 )
					t = rotateWithLeftChild( t );
				else
					t = doubleWithLeftChild( t );
		}
		else if( x.compareTo( t.element ) > 0 )
		{
			t.right = insert( x, t.right );
			if( height( t.right ) - height( t.left ) == 2 )
				if( x.compareTo( t.right.element ) > 0 )
					t = rotateWithRightChild( t );
				else
					t = doubleWithRightChild( t );
		}
		else
			;  // Duplicate; do nothing
		t.height = max( height( t.left ), height( t.right ) ) + 1;
		return t;
	}


	/**
	 * Return the height of node t, or -1, if null.
	 */
	private static int height( AVLNode t )
	{
		return t == null ? -1 : t.height;
	}

	/**
	 * Return maximum of lhs and rhs.
	 */
	private static int max( int lhs, int rhs )
	{
		return lhs > rhs ? lhs : rhs;
	}

	/**
	 * Rotate binary tree node with left child.
	 * For AVL trees, this is a single rotation for case 1.
	 * Update heights, then return new root.
	 */
	private static AVLNode rotateWithLeftChild( AVLNode k2 )
	{
		AVLNode k1 = k2.left;
		k2.left = k1.right;
		k1.right = k2;
		k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
		k1.height = max( height( k1.left ), k2.height ) + 1;
		return k1;
	}

	/**
	 * Rotate binary tree node with right child.
	 * For AVL trees, this is a single rotation for case 4.
	 * Update heights, then return new root.
	 */
	private static AVLNode rotateWithRightChild( AVLNode k1 )
	{
		AVLNode k2 = k1.right;
		k1.right = k2.left;
		k2.left = k1;
		k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
		k2.height = max( height( k2.right ), k1.height ) + 1;
		return k2;
	}

	/**
	 * Double rotate binary tree node: first left child
	 * with its right child; then node k3 with new left child.
	 * For AVL trees, this is a double rotation for case 2.
	 * Update heights, then return new root.
	 */
	private static AVLNode doubleWithLeftChild( AVLNode k3 )
	{
		k3.left = rotateWithRightChild( k3.left );
		return rotateWithLeftChild( k3 );
	}

	/**
	 * Double rotate binary tree node: first right child
	 * with its left child; then node k1 with new right child.
	 * For AVL trees, this is a double rotation for case 3.
	 * Update heights, then return new root.
	 */
	private static AVLNode doubleWithRightChild( AVLNode k1 )
	{
		k1.right = rotateWithLeftChild( k1.right );
		return rotateWithRightChild( k1 );
	}
	
	private LinkedList<Comparable> ListFound; 
	
	@SuppressWarnings("unchecked")
	public LinkedList<Comparable> findAll( Comparable x){
		 ListFound = new LinkedList<Comparable>();
		 
		AVLNode t=root;
		while( t != null ){
			if( x.compareTo( t.element ) < 0 )
				t = t.left;
			else if( x.compareTo( t.element ) > 0 )
				t = t.right;
			else {
				findIfFound(x,t);
				break;
			}
		}
		return ListFound;
	}

	@SuppressWarnings("unchecked")
	private void findIfFound(Comparable x, AVLNode t) {
		
		if (x.compareTo(t.element)==0){
			ListFound.add(t.element);
			if(t.left!=null)
			findIfFound(x,t.left);
			if(t.right!=null)
			findIfFound(x,t.right);
		}
	}	
	
}
